{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Before and After Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beforeAndAfterPuzzles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #前后拼接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个「短语」列表&nbsp;<code>phrases</code>，请你帮忙按规则生成拼接后的「新短语」列表。</p>\n",
    "\n",
    "<p>「短语」（phrase）是仅由小写英文字母和空格组成的字符串。「短语」的开头和结尾都不会出现空格，「短语」中的空格不会连续出现。</p>\n",
    "\n",
    "<p>「前后拼接」（Before and After&nbsp;puzzles）是合并两个「短语」形成「新短语」的方法。我们规定拼接时，<strong>第一个短语的最后一个单词</strong> 和 <strong>第二个短语的第一个单词</strong> 必须相同。</p>\n",
    "\n",
    "<p>返回每两个「短语」&nbsp;<code>phrases[i]</code>&nbsp;和&nbsp;<code>phrases[j]</code>（<code>i != j</code>）进行「前后拼接」得到的「新短语」。</p>\n",
    "\n",
    "<p>注意，两个「短语」拼接时的顺序也很重要，我们需要同时考虑这两个「短语」。另外，同一个「短语」可以多次参与拼接，但「新短语」不能再参与拼接。</p>\n",
    "\n",
    "<p>请你按字典序排列并返回「新短语」列表，列表中的字符串应该是 <strong>不重复的</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>phrases = [&quot;writing code&quot;,&quot;code rocks&quot;]\n",
    "<strong>输出：</strong>[&quot;writing code rocks&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>phrases = [&quot;mission statement&quot;,\n",
    "                &quot;a quick bite to eat&quot;,\n",
    "&nbsp;               &quot;a chip off the old block&quot;,\n",
    "&nbsp;               &quot;chocolate bar&quot;,\n",
    "&nbsp;               &quot;mission impossible&quot;,\n",
    "&nbsp;               &quot;a man on a mission&quot;,\n",
    "&nbsp;               &quot;block party&quot;,\n",
    "&nbsp;               &quot;eat my words&quot;,\n",
    "&nbsp;               &quot;bar of soap&quot;]\n",
    "<strong>输出：</strong>[&quot;a chip off the old block party&quot;,\n",
    "&nbsp;     &quot;a man on a mission impossible&quot;,\n",
    "&nbsp;     &quot;a man on a mission statement&quot;,\n",
    "&nbsp;     &quot;a quick bite to eat my words&quot;,\n",
    "      &quot;chocolate bar of soap&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>phrases = [&quot;a&quot;,&quot;b&quot;,&quot;a&quot;]\n",
    "<strong>输出：</strong>[&quot;a&quot;]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= phrases.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= phrases[i].length &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [before-and-after-puzzle](https://leetcode.cn/problems/before-and-after-puzzle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [before-and-after-puzzle](https://leetcode.cn/problems/before-and-after-puzzle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"writing code\",\"code rocks\"]', '[\"mission statement\",\"a quick bite to eat\",\"a chip off the old block\",\"chocolate bar\",\"mission impossible\",\"a man on a mission\",\"block party\",\"eat my words\",\"bar of soap\"]', '[\"a\",\"b\",\"a\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        suf = []\n",
    "        pre = defaultdict(list)\n",
    "        ans = []\n",
    "        for i, x in enumerate(phrases):\n",
    "            a = x.split()\n",
    "            pre[a[0]].append(i)\n",
    "            suf.append(a[-1])\n",
    "\n",
    "        for i, x in enumerate(phrases):\n",
    "            k = suf[i]\n",
    "            s = x[0:len(x)-len(k)]\n",
    "            for j in pre[k]:\n",
    "                if i != j:\n",
    "                    ans.append(s + phrases[j])\n",
    "        ans = list(set(ans))\n",
    "        ans.sort()\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        n = len(phrases)\n",
    "        idx_s_w = defaultdict(list)\n",
    "        for i, p in enumerate(phrases):\n",
    "            tmp = p.split()\n",
    "            idx_s_w[i] = [tmp[0],tmp[-1]]\n",
    "        match = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i==j: continue\n",
    "                if idx_s_w[i][1] == idx_s_w[j][0]:\n",
    "                    new_p = phrases[i]+phrases[j][len(idx_s_w[j][0]):]\n",
    "                    match.add(new_p)\n",
    "        res = list(match)\n",
    "        res = sorted(res)\n",
    "        # res.sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        srtdict, enddict, res = defaultdict(set), defaultdict(set), set()\n",
    "        for word in phrases:\n",
    "            n, i = len(word), 0\n",
    "            while i < n and word[i] != ' ': i += 1\n",
    "            srt = word[:i]\n",
    "            if srt in enddict:\n",
    "                for srtword in enddict[srt]: res.add(srtword + word[i:])\n",
    "            i = n - 1\n",
    "            while i >= 0 and word[i] != ' ': i -= 1\n",
    "            end = word[i + 1:]\n",
    "            if end in srtdict:\n",
    "                for endword in srtdict[end]: res.add(word[:i + 1] + endword)\n",
    "            srtdict[srt].add(word)\n",
    "            enddict[end].add(word)\n",
    "        return sorted(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        phrases = [p.split(\" \") for p in phrases]\n",
    "        n = len(phrases)\n",
    "        ans = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and phrases[i][-1] == phrases[j][0]:\n",
    "                    ans.add(\" \".join(phrases[i][:-1] + phrases[j]))\n",
    "        return sorted(list(ans))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        n=len(phrases)\n",
    "        ans=set()\n",
    "        for i in range(n):\n",
    "            l=phrases[i].split(' ')\n",
    "            for j in range(n):\n",
    "                if i==j:continue\n",
    "                r=phrases[j].split(' ')\n",
    "                if l[-1]==r[0]:\n",
    "                    ans.add(\" \".join(l+r[1:]))\n",
    "        return sorted(list(ans))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        p = [a.split(\" \") for a in phrases]\n",
    "        jie = set()\n",
    "        n = len(phrases)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and p[i][-1]==p[j][0]:\n",
    "                    jie.add(\" \".join(p[i][:-1]+p[j]))\n",
    "        return sorted(jie)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        hashmap1 = defaultdict(list)\n",
    "        hashmap2 = defaultdict(list)\n",
    "        res = []\n",
    "        for p in phrases:\n",
    "            listP = p.split(\" \")\n",
    "            prefix = listP[0]\n",
    "            suffix = listP[-1]\n",
    "            for list2 in hashmap2[prefix]:\n",
    "                res.append(\" \".join(list2+listP[1:]))\n",
    "            for list2 in hashmap1[suffix]:\n",
    "                res.append(\" \".join(listP+list2[1:]))\n",
    "\n",
    "            hashmap1[prefix].append(listP)\n",
    "            hashmap2[suffix].append(listP)\n",
    "        \n",
    "        \n",
    "        \n",
    "        return sorted(list(set(res)))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "      before = collections.defaultdict(set)\n",
    "      after = collections.defaultdict(set)\n",
    "      n = len(phrases)\n",
    "\n",
    "      for i in range(n):\n",
    "        phrases[i] = phrases[i].split()\n",
    "        before[phrases[i][0]].add(i)\n",
    "        after[phrases[i][-1]].add(i)\n",
    "      \n",
    "      ans = set()\n",
    "      for word in set(before.keys()) & set(after.keys()):\n",
    "        for i in before[word]:\n",
    "          for j in after[word]:\n",
    "            if i != j:\n",
    "              ans.add(\" \".join(phrases[j][:-1] + phrases[i]))\n",
    "      \n",
    "      return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        dstart=defaultdict(list)\n",
    "        dend=defaultdict(list)\n",
    "        ans=set()\n",
    "        for i,k in enumerate(phrases):\n",
    "            kk=k.split(\" \")\n",
    "            start=kk[0]\n",
    "            end=kk[-1]\n",
    "            if end in dstart:\n",
    "                for x in dstart[end]:\n",
    "                    temp=phrases[x].split(\" \")\n",
    "                    if len(temp)==1:\n",
    "                        ans.add(k)\n",
    "                    else:\n",
    "                        ans.add(k+\" \"+\" \".join(temp[1:]))\n",
    "            if start in dend:\n",
    "                for y in dend[start]:\n",
    "                    temp=phrases[y]\n",
    "                    if len(kk)==1:\n",
    "                        ans.add(temp)\n",
    "                    else:\n",
    "                        ans.add(temp+\" \"+\" \".join(kk[1:]))\n",
    "            dstart[start].append(i)\n",
    "            dend[end].append(i)\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "      before = collections.defaultdict(set)\n",
    "      after = collections.defaultdict(set)\n",
    "      n = len(phrases)\n",
    "\n",
    "      for i in range(n):\n",
    "        phrases[i] = phrases[i].split()\n",
    "        before[phrases[i][0]].add(i)\n",
    "        after[phrases[i][-1]].add(i)\n",
    "      \n",
    "      ans = set()\n",
    "      for word in set(before.keys()) & set(after.keys()):\n",
    "        for i in before[word]:\n",
    "          for j in after[word]:\n",
    "            if i != j:\n",
    "              ans.add(\" \".join(phrases[j][:-1] + phrases[i]))\n",
    "      \n",
    "      return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "      before = collections.defaultdict(set)\n",
    "      after = collections.defaultdict(set)\n",
    "      n = len(phrases)\n",
    "\n",
    "      for i in range(n):\n",
    "        phrases[i] = phrases[i].split()\n",
    "        before[phrases[i][0]].add(i)\n",
    "        after[phrases[i][-1]].add(i)\n",
    "      \n",
    "      ans = set()\n",
    "      for word in set(before.keys()) & set(after.keys()):\n",
    "        for i in before[word]:\n",
    "          for j in after[word]:\n",
    "            if i != j:\n",
    "              ans.add(\" \".join(phrases[j][:-1] + phrases[i]))\n",
    "      \n",
    "      return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        phrases = [p.split(\" \") for p in phrases]\n",
    "        n = len(phrases)\n",
    "        ans = set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and phrases[i][-1] == phrases[j][0]:\n",
    "                    ans.add(\" \".join(phrases[i][:-1] + phrases[j]))\n",
    "        return sorted(list(ans))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beforeAndAfterPuzzles(self, phrases: List[str]) -> List[str]:\n",
    "        phrases=[p.split(' ') for p in phrases]\n",
    "        n=len(phrases)\n",
    "        ans=set()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j and phrases[i][-1]==phrases[j][0]:\n",
    "                    ans.add(' '.join(phrases[i][:-1]+phrases[j]))\n",
    "        return sorted(list(ans))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
